/**
 * 合并k个升序链表
 * 
 */
class MergeKListsn {
    public ListNode mergeKLists(ListNode[] lists) {
        int len=lists.length;
        if(len==0){
            return null;
        }
        if(len==1){
            return lists[0];
        }
        ListNode head=merge(lists[0],lists[1]);
        for(int i=2;i<len;i++){
            head=merge(head,lists[i]);
        }
        return head;
    }
    public ListNode merge(ListNode headA,ListNode headB){
       ListNode newHead=new ListNode();
       ListNode cur=newHead;
       while(headA!=null&&headB!=null){
           if(headA.val<headB.val){
               cur.next=headA;
               cur=headA;
               headA=headA.next;
           }else{
               cur.next=headB;
               cur=headB;
               headB=headB.next;
           }
       }
       if(headB!=null){
           cur.next=headB;
       }
       if(headA!=null){
           cur.next=headA;
       }
       return newHead.next;
    }
}